{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第11章 搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.1 二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "树型数据结构的一个重要用途是用作搜索树，可以使用搜索树结构实现有序映射（中序遍历后与排序检索表是一致的，二叉搜索算法支持精确搜索，before(p)等方法依托于中序遍历结合搜索结果来实现不精确搜索——有序映射的特点就是不精确搜索，因为精确搜索用哈希表可以达到O(1)，没必要用有序映射）。映射的特点是通过键找到值，因此最重要的一点就是搜索，依靠哈希表将键和数组的索引链接起来可以达到O(1)的搜索时间，依靠有序数组+二分查找或者跳跃表可以达到O(log(n))的搜索时间，而且实现的是有序映射，因此对于映射或者有序映射来说，最重要的就是搜索，很常用的就是二分查找的思想。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二叉搜索树：每个节点存储一个键值对元组的二叉树（单单用于搜索，可以直接存储一个数而不是键值对元组），对于一个节点p，存储在p的左子树的键都小于p的键，右子树的键都大于p的键。（存储键值对元组可以用于实现有序映射，如果每个节点只存储一个数，那么估计相当于二分查找）\n",
    "\n",
    "注：值不影响键值对元组在二叉搜索树中的位置，一切的搜索和插入也是根据键来的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 11.1.1 遍历二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二叉搜索树中序遍历是按照键增加的顺序进行的。（愈发地像一个排序检索表，或者说一个排序的数组）（这个命题通过递归的思想可以很容易地证明）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二叉搜索树中序遍历需要O(n)，也就是二叉搜索树可以在O(n)时间内产生一个有序的迭代器，这也很像排序数组，不排序的数组可能需要O($n^2$)或者O(nlog(n))。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二叉搜索树比二叉树额外支持的方法：\n",
    "\n",
    "1. first(): 返回一个包含最小键的节点，树为空则返回None。\n",
    "2. last(): 同上，改为最大。\n",
    "3. before(p): 返回比键比p的键小的所有节点中键最大的节点。如果p是第一个节点，返回None。（第一个节点就是键最小的节点）\n",
    "4. after(p): 键比p的键大的最小键对应的节点。如果p是最后一个节点，返回None。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " 在找after和before的时候，其实就是根据中序遍历，因为中序遍历出来就是有序的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3，4方法摊销运行时间为O(1)，因为做一次中序遍历需要O(n)，n个节点都知道了，所以平均下来为O(1)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 11.1.2 搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在二叉搜索树中搜索一个键（如果存储的不是元组，也可以搜索一个值）使用的是二叉搜索算法：每次将节点的键与要搜索的键进行比较，如果节点键小了，搜索节点的右子树，如果节点键大了，搜索节点的左子树，如果相等，搜索结束，如果接下来要搜索的子树为空，那么结果为没有这个键。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二叉搜索算法的时间复杂度为O(h)。（每次都下降一层，最差的情况下有h+1次比较）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 11.1.3 插入和删除"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "插入支持的方法：M\\[k\\]=v（与map保持一致）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二叉搜索算法支持M\\[k\\]，如果搜索到则重新赋值，搜索不到则插入一个新节点。（搜索不到，则插入为返回的节点的子节点，搜索到的空树被新的节点代替）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "删除支持的方法：del M\\[k\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "搜索不到M\\[k\\]则报错，搜索得到，删除的操作会比较复杂。\n",
    "\n",
    "如果搜索成功，分两种情况：\n",
    "\n",
    "1. p没有子节点或者只有一个子节点：直接删除，如果有子节点，直接将子节点与父节点连接起来。\n",
    "2. p有两个子节点，找到p的before记为r，显然r的键要大于p的左子树小于p的右子树，所以用r的键值对换掉p的，然后删除r节点（p有两个子节点，按照中序遍历，p的before是是左子树）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 11.1.4 Python实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeMap(LinkedBinaryTree, MapBase):\n",
    "\n",
    "    class Position(LinkedBinaryTree.Position):\n",
    "\n",
    "        def key(self):\n",
    "            return self.element()._key\n",
    "\n",
    "        def value(self):\n",
    "            return self.element()._value\n",
    "\n",
    "    def _subtree_search(self, p, k):\n",
    "        if k == p.key():\n",
    "            return p\n",
    "        elif k < p.key():\n",
    "            if self.left(p):\n",
    "                return self._subtree_search(self.left(p), k)\n",
    "        else:\n",
    "            if self.right(p):\n",
    "                return self._subtree_search(self.right(p), k)\n",
    "        return p                             ## 搜索不到，返回最后一个位置，如果插入新元素将是这个位置的子节点\n",
    "\n",
    "    def _subtree_first_position(self, p):    ## 最小的节点，一直找左节点\n",
    "        walk = p\n",
    "        while self.left(p):\n",
    "            walk = self.left(p)\n",
    "        return walk\n",
    "\n",
    "    def _subtree_last_position(self, p):     ## 一般定义用于子树的非公有方法，之后会递归调用\n",
    "        walk = p\n",
    "        while self.right(p):\n",
    "            p = self.right(p)\n",
    "        return walk\n",
    "\n",
    "    def first(self):\n",
    "        return self._subtree_first_position(self.root())\n",
    "\n",
    "    def last(self):\n",
    "        return self._subtree_last_position(self.root())\n",
    "\n",
    "    def before(self, p):\n",
    "        self._validate(p)\n",
    "        if self.left(p):\n",
    "            return self._subtree_last_position(self.left(p))\n",
    "        walk = p\n",
    "        walk_parent = self.parent(p)\n",
    "        while walk_parent is not None and walk == self.left(walk_parent):   ## 如果None，说明是最左边的节点\n",
    "            walk, walk_parent = walk_parent, self.parent(walk_parent)\n",
    "        return walk_parent\n",
    "\n",
    "    def after(self, p):\n",
    "        self._validate(p)\n",
    "        if self.right(p):\n",
    "            return self._subtree_first_position(self.right(p))\n",
    "        walk = p\n",
    "        walk_parent = self.parent(p)\n",
    "        while walk_parent is not None and walk == self.right(walk_parent):  ## 如果None，说明是最右边的节点\n",
    "            walk, walk_parent = walk_parent, self.parent(walk_parent)\n",
    "        return walk_parent\n",
    "\n",
    "    def find_position(self, k):\n",
    "        if self.is_empty():\n",
    "            return None\n",
    "        p = self._subtree_search(self.root(), k)\n",
    "        self._rebalance_access(p)                      ## 子类平衡树的hook\n",
    "        return p\n",
    "\n",
    "    def find_min(self):\n",
    "        if self.is_empty():\n",
    "            return None\n",
    "        p = self.first()\n",
    "        return p.key(), p.value()\n",
    "\n",
    "    def find_ge(self, k):\n",
    "        if self.is_empty():\n",
    "            return None\n",
    "        p = self._subtree_search(self.root(), k)       ## 如果p.key() >= k，那么p是对的\n",
    "        if p.key() < k:                                ## p.key() < k，p需要更改\n",
    "            p = self.after(p)                          ## 找不到的话，k也必然夹在两个节点之间\n",
    "        return p.key(), p.value() if p else None\n",
    "\n",
    "    def find_range(self, start, stop):\n",
    "        if not self.is_empty():\n",
    "            if start is None:\n",
    "                p = self.first()\n",
    "            else:\n",
    "                p = self.find_position(start)\n",
    "                if p.key() < start:\n",
    "                    p = self.after(p)                  ## 找到起始节点，一直after直到stop\n",
    "        while p is not None and (stop is None or p.key() < stop):\n",
    "            yield p.key(), p.value()\n",
    "            p = self.after(p)\n",
    "\n",
    "    def __getitem__(self, k):\n",
    "        if self.is_empty():\n",
    "            raise ValueError('Key Error: ' + repr(k))\n",
    "        p = self._subtree_search(self.root(), k)\n",
    "        self._rebalance_access(p)                      ## 子类平衡树的方法\n",
    "        if p.key() != k:\n",
    "            raise ValueError('Key Error: ' + repr(k))\n",
    "        return p.value()\n",
    "\n",
    "    def __setitem__(self, k, v):\n",
    "        if self.is_empty():\n",
    "            leaf = self._add_root(self._Item(k, v))    ## 继承的_Item类\n",
    "        else:\n",
    "            p = self._subtree_search(self.root(), k)\n",
    "            if p.key() == k:\n",
    "                p.element()._value = v\n",
    "                self._rebalance_access(p)\n",
    "                return\n",
    "            else:\n",
    "                item = self._Item(k, v)\n",
    "                if p.key() < k:\n",
    "                    leaf = self._add_right(p, item)\n",
    "                else:\n",
    "                    leaf = self._add_left(p, item)\n",
    "        self._rebalance_insert(leaf)\n",
    "\n",
    "    def __iter__(self):\n",
    "        p = self.first()\n",
    "        while p is not None:\n",
    "            yield p.key()\n",
    "            p = self.after(p)                          ## 中序遍历的非递归实现\n",
    "\n",
    "    def delete(self, p):\n",
    "        self._validate(p)\n",
    "        if self.left(p) and self.right(p):             ## 两个子节点\n",
    "            replacement = self._subtree_last_position(self.left(p))\n",
    "            self._replace(p, replacement.element())\n",
    "        parent = self.parent(p)\n",
    "        self._delete(p)\n",
    "        self._rebalance_delete(parent)\n",
    "\n",
    "    def __delitem__(self, k):\n",
    "        if not self.is_empty():\n",
    "            p = self._subtree_search(self.root(), k)\n",
    "            if k == p.key():\n",
    "                self.delete(p)\n",
    "                return\n",
    "            self._rebalance_access(p)\n",
    "        raise KeyError('Key Error' + repr(k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二叉搜索树（TreeMap）各方法时间复杂度（依赖于树的高度h）：\n",
    "\n",
    "操作 | 运行时间\n",
    ":-: | :-: \n",
    "k in T | O(h)\n",
    "T\\[k\\], T\\[k\\] = v | O(h)\n",
    "T.delete(p), del T\\[k\\] | O(h)\n",
    "T.find_position(k) | O(h)\n",
    "T.first(), T.last(), T.find_min(), T.find_max() | O(h)\n",
    "T.before(p), T.after(p) | O(h)\n",
    "T.find_lt(k), T.find_le(k), T.find_gt(k), T.find_ge(k) | O(h)\n",
    "T.find_range(start, stop) | O(s + h)\n",
    "iter(T), reversed(T) | O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "find_range方法中的h是search带来的，s是s个after方法带来的，虽然单个after方法最差情况下需要O(h)，但是只需要O(n)时间调用iter就可以实现n次after，因此摊销后after方法的时间复杂度为O(1)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.2 平衡搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二叉搜索树的方法效率与树的高度有关，有些情况下树的高度可能为O(n)，这将导致二叉搜索树效率低下。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "平衡二叉搜索树定义了旋转操作。详见313页。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以将一个或多个旋转合并来提供更广泛的平衡，称为trinode重组。详见314页。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "平衡搜索树相比标准二叉搜索树，多出了三个非公开的方法：（不一定都是AVL树的，还有伸展树的，糅合在了一起）\n",
    "\n",
    "1. 添加新节点，需要调用`_rebalance_delete(p)`方法。\n",
    "2. 删除一个节点，需要调用`_rebalance_delete(self.parent(p))`。\n",
    "3. 访问一个节点，需要调用`_rebalance_access(p)`，用于伸展树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以上的非公有方法在标准二叉搜索树中只声明函数名，函数体直接pass，这是模板方法设计模式。（对标准二叉搜索树不会有影响，因为pass，起的作用的先给后面子类AVL树和伸展树声明了一个框架，可以在这两类树中具体实现这三个非公有方法）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _rebalance_insert(self, p):\n",
    "    pass\n",
    "    \n",
    "def _rebalance_delete(self, p):\n",
    "    pass\n",
    "    \n",
    "def _rebalance_access(self, p):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于旋转和trinode重组，可以在标准二叉搜索树中先实现，之后子类实现三个非公有办法，直接调用标准二叉搜索树的旋转和trinode重组方法即可，不用再重复编写。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _relink(self, parent, child, make_left_child):        ## 用于旋转\n",
    "    if make_left_child:\n",
    "        parent._left = child\n",
    "    else:\n",
    "        parent._right = child\n",
    "    if child is not None:\n",
    "        child._parent = parent\n",
    "\n",
    "def _rotate(self, p):                                     ## 用于旋转，p是最下面的位置\n",
    "    x = p._node\n",
    "    y = x._parent\n",
    "    z = y._parent\n",
    "    if z is None:                                         ## 说明y现在是root，x即将成为root\n",
    "        self._root = x\n",
    "        x._parent = None\n",
    "    else:\n",
    "        self._relink(z, x, y == z._left)                  ## y为left，那x为left\n",
    "    if x == y._left:                                      ## 现在y的left或者right还连着x\n",
    "        self._relink(y, x._right, True)                   ## x为y的left，那么x的right变成y的left\n",
    "        self._reline(x, y, False)                         ## x为y的left，那么y变成x的right\n",
    "    else:\n",
    "        self._relink(y, x._left, False)\n",
    "        self._relink(x, y, True)\n",
    "\n",
    "def _restructure(self, x):                                ## 输入的x是node不是position\n",
    "    y = self.parent(x)\n",
    "    z = self.parent(y)\n",
    "    if (x == self.right(y)) == (y == self.right(z)):      ## 同左或者同右，只需要一次旋转\n",
    "        self._rotate(y)\n",
    "        return y\n",
    "    else:                                                 ## 一左一右，需要两次旋转\n",
    "        self._rotate(x)\n",
    "        self._rotate(x)    \n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里旋转和trinode重组已经想通了，旋转基于两个节点，trinode重组基于三个节点，二者将两个节点和三个节点的重组都囊括在内，这并不难，难的是如何去判断，什么时候应该调用旋转操作，即难的是在子类中实现三个_rebalance非公有方法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.3 AVL树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据理解，前面的平衡树是后面这几类树的总称，至于用如何rebalance和如何实现，那是由不同子类来体现的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "任何满足`高度平衡属性`的二叉搜索树都被称为AVL树。\n",
    "\n",
    "高度平衡属性：对于T中每一个位置p，p的孩子的高度最多相差1。、\n",
    "\n",
    "很容易看出，AVL的子树也都是AVL树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "证明AVL树高度为O(log(n)):\n",
    "\n",
    "思路是如果高度为h，AVL树至少有多少个节点，只需证明节点数为指数级。一般有关树的证明，要多考虑递归（类似数学归纳法，将n分解为n-1或者更小的），可以列出式子：\n",
    "\n",
    "n(h) = n(h - 1) + n(h - 2) + 1\n",
    "\n",
    "因为最少节点，所以子树高度不会一样，肯定是一大一小。\n",
    "\n",
    "因为n(h - 1) > n(h - 2)，所以n(h) > 2n(h - 2)，所以是指数级。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.3.1 更新操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "插入：插入一个新节点可能会破坏高度平衡属性，因此在AVL树更新时，需要进行再平衡：首先找到因为插入新节点p而导致发生不平衡的第一个节点（即该节点的两个子节点高度相差超过1），记为z，令y为z的高度更高的子节点，令x为y的高度更高的子节点，然后调用方法restructure(x)即可。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这种再平衡能够恢复全局高度平衡属性的证明在318—319页。其中比较重要的一点是，根据x，y，z的设定，y目前是平衡的，但是y的高度相比之前增大了，且x是y高度较大的子节点，说明x的高度相比之前增大了（要么x之前不存在，现在变成新节点，高度从0变成1，要么x下面原来具有相同高度的子树，其中一个高度增大了，因为插入了新节点），且之前x的节点与另一个子节点高度相等（否则y的高度不会增大），在前面的前提下，可以构造出插入前后的二叉树，然后再对旋转操作进行分类讨论，即可证明。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "删除：删除操作可能导致删除节点p所在的子树高度变小，首先往父节点搜索，找到第一个不平衡的节点，记为z，然后令y为z的高度更大的子节点，显然y不是p所在的子树，而是另一棵子树，这说明y的高度原来就比p所在的子树要大1，如果y的两个子节点高度不一样，令x为高度更大的子节点（方便进行trinode重组），如果y的两个子节点高度一样，那么如果y为z左，令x为y左，y为z右，令x为y右（如果不这样选，那么需要进行两次旋转，在第一次旋转的时候，x的子树变成y的子树，可能导致不平衡，举个例子，x高度为h，两个子树分别为h - 1和h - 2，如果将h - 2的旋转之后变为y子树，那么y就不平衡，而如果令x和y在同一边，那么只进行一次旋转，且一定不会导致不平衡），然后执行restructure(x)。对上述几种情况进行分类讨论，可以发现进行restructure(x)之后，相比之前（之前是指还没有删除节点之前），以z为根的子树高度要么不变要么增大1（过程被我画在附录B），因此可能进一步造成z的祖先节点等不平衡，然后对z的祖先节点继续进行上面的操作，直至达到根节点，才能达到全局的平衡。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上述p不一定是搜索到的节点，如果搜索到的节点有左右子树，这种情况下，p是左子树的最右节点，这一点从TreeMap类中delete方法中p的取值可以看出。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "AVL树各方法的时间复杂度：与标准二叉搜索树相同，只是h确定能被限制为log(n)，所以基本上所有方法的执行时间都在O(log(n))，至于插入和删除操作，可以很显然地看到，一次trinode重组只需要O(1)的时间，插入只需要1次，删除最多log(n)次，所以最后时间复杂度还是在O(log(n))。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 11.3.2 Python实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class AVLTreeMap(TreeMap):\n",
    "\n",
    "    class _Node(TreeMap._Node):\n",
    "\n",
    "        __slots__ = '_height'                       ## 新增一个height\n",
    "\n",
    "        def __init__(self, element, parent=None, left=None, right=None):\n",
    "            super().__init__(element, parent, left, right)\n",
    "            self._height = 0                        ## 新建节点只在插入新节点时，必为叶子节点，所以高度为0\n",
    "\n",
    "        def left_height(self):\n",
    "            return self._left._height if self._left else 0\n",
    "\n",
    "        def right_height(self):\n",
    "            return self._right._height if self._right else 0\n",
    "\n",
    "    def _recompute_height(self, p):                  ## 重新计算节点的高度，插入和删除会对其他节点的高度造成影响\n",
    "        p._node._height = 1 + max(p._node.left_height(), p._node.right_height())\n",
    "\n",
    "    def _isbalanced(self, p):                        ## 判断一个节点是否平衡\n",
    "        return abs(p._node.left_height() - p._node.right_height()) <= 1\n",
    "\n",
    "    def _tall_child(self, p, favorleft=False):       ## 左高则取左，相等则取决于favorleft，favorleft取决于p是左还是右\n",
    "        if p._node.left_height + (1 if favorleft else 0) > p._node.right_height():\n",
    "            return self.left(p)\n",
    "        else:\n",
    "            return self.right(p)\n",
    "    \n",
    "    def _tall_grandchild(self, p):\n",
    "        child = self._tall_child(p)                  ## 这个方法在p不平衡的情况下调用，所以不需要favorleft\n",
    "        aligment = (child == self.left(p))\n",
    "        return self._tall_child(child, aligment)\n",
    "\n",
    "    def _rebalance(self, p):                         ## p是插入的新节点或者删除的节点的父节点\n",
    "        while p:\n",
    "            old_height = p._node._height\n",
    "            if not self._isbalanced(p):\n",
    "                p = self._restructure(self._tall_grandchild(p)) ## restructure返回的是trinode重组后子树的根节点\n",
    "                self._recompute_height(self.left(p))  ## trinode重组不涉及子树（子树整个移动），只可能对3个节点高度有影响\n",
    "                self._recompute_height(self.right(p))\n",
    "            self._recompute_height(p)                           \n",
    "            if p._node._height == old_height:         ## 如果重组后高度没变，那么就不会再破坏祖先节点的平衡了\n",
    "                p = None\n",
    "            else:\n",
    "                p = self.parent(p)\n",
    "    \n",
    "    def _rebalance_insert(self, p):\n",
    "        self._rebalance(p)\n",
    "    \n",
    "    def _rebalance_delete(self, p):\n",
    "        self._rebalance(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.4 伸展树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "伸展树（splay tree）：不像AVL树一样对树的高度有高度平衡属性的限制，伸展树与标准二叉搜索树的不同在于，伸展树每次搜索一个节点后，会将该节点不停旋转直至到达根节点。共有三种旋转的方式，分别为zig-zig型（2次旋转），zig-zag型（2次）和zig型（1次），详见书上322页。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "伸展树可以保障插入、删除和搜索操作具有对数运行时间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 11.4.2 何时进行伸展"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 搜索键k时，如果在位置p找到了键k，则伸展p；否则伸展搜索到的叶子节点。\n",
    "* 插入键k时，伸展新插入的节点。\n",
    "* 删除键k时，伸展被删除节点的父节点。（这里的被删除的节点分两种情况，如果键k对应的节点有左右子树，则被删除的节点是左子树的最右节点，如果键k对应的节点不是左右子树都有，那么被删除的节点为键k对应的节点）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SplayTreeMap(TreeMap):\n",
    "\n",
    "    def _splay(self, p):\n",
    "        while p != self.root():\n",
    "            parent = self.parent(p)\n",
    "            grand = self.parent(parent)\n",
    "            if grand is None:          ## zig\n",
    "                self._rotate(p)\n",
    "            elif (parent == self.left(grand)) and (p == self.left(parent)):      ## zig-zig\n",
    "                self._rotate(parent)              ## parent为左子则右旋，右子则左旋\n",
    "                self._rotate(p)\n",
    "            else:                      ## zig-zag\n",
    "                self._rotate(x)\n",
    "                self._rotate(x)\n",
    "    \n",
    "    def _rebalance_insert(self, p):    ## 与AVL树不同的再平衡方法，这里再平衡是进行伸展，AVL树是进行trinode重组\n",
    "        self._splay(p)\n",
    "    \n",
    "    def _rebalance_delete(self, p):\n",
    "        if p is not None:\n",
    "            self._splay(p)\n",
    "    \n",
    "    def _rebalance_access(self, p):\n",
    "        self._splay(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "三个`rebalance`方法，分别对应搜索、插入、删除，在TreeMap类已经给出框架，并且揉入到了TreeMap类的搜索、插入和删除中，只不过是pass而已，AVL树和伸展树各有自己不同的`rebalance`法则，定义了不同的非公开方法进行支持，但是他们都会用到旋转（rotate）操作，即左旋和右旋，因此在TreeMap类中已经给出了左旋和右旋的实现，甚至还给出了trinode重组的实现，只不过trinode重组只被用在AVL树中而已。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.5 （2，4）树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里的名称与正常的不太一样，正常的有（2，3）树和（2，3，4）树两种。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有关（2，3）树和（2，3，4）树的定义，可以参考[https://www.w3xue.com/exp/article/20192/20400.html](https://www.w3xue.com/exp/article/20192/20400.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. （2，3，4）树中有3种节点，先称为2节点、3节点和4节点，2节点存储一个键值，有两个子节点；3节点存储两个键值，有三个子节点；4节点存储三个键值，有四个子节点。\n",
    "2. （2，3，4）树对键值存储的顺序是有要求的，对于键值为k的2节点，左子节点小于键值k，右子节点大于键值k，对于键值为k1和k2的3节点，左中右被k1和k2划分的三个区间覆盖，4节点同理。\n",
    "3. 所有叶子节点有相同的深度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "节点中可能需要存储多个键值，这时可以用有序映射作为二级数据结构，虽然整个（2，3，4）树是为了实现有序映射（也有可能只有键没有值，我们先统称为有序映射），其实中序遍历之后就很像排序检索表，只不过每个元素可能是一个更小的排序检索表。这里二级数据结构采用排序检索表实现的有序映射，因此每次搜索键值k，不仅仅需要树的高度，还需要在每个节点内进行基于二分查找的搜索（时间O(log(d))），所以（2，3，4）树的搜索时间为O(hd)，由于d最大为3，所以还是O(h)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "（2，3，4）树对d的限制为内部节点的子节点最多有4个，对高度的限制在于，所有外部节点的深度相同，这实际上对高度进行了限制。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "证明对数高度：\n",
    "\n",
    "引用结论，有n个节点（有效节点）的（2，3，4）树有n + 1个外部节点，高度为h的树，最多有$4^h$，最少有$2^h$个外部节点，从这里就可以看出指数关系。另一个直观的想法是，同样节点数量，（2，3，4）树的高度比每一层都满的完全二叉树要低，所以一定是对数高度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "（2，3，4）树的插入：找到叶子节点上面一层，插入到相应位置，如果该节点存储的键超过了3个，那么将第3个键拿出来，放到父节点中，这时父节点多一个键意味着多一个子节点，正好下面的节点因为第3个拿掉分成两个子节点，左边的存储两个键带三个子节点，右边的存储一个键带两个子节点。这里很巧妙的地方在于，从第三个分开后，虽然下面存储的键数少了，但是分成两个子节点，可以带的外部节点还是一样多，分成两个子节点刚好需要父节点多一条线，因为第三个上去了，刚好多一条线。这里分情况，如果上去之后父节点不存储超过三个键值，那就结束，如果超过了三个，那么继续分裂；如果根节点超过了三个，那么原根节点的第三个键将变成新的根节点，这也是（2，3，4）树中从空树连续插入很多个值的过程。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "空树，插入3个元素后，第4个元素插入将会导致新的根节点的诞生。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "（2，3，4）树的搜索：从根节点开始，找到自己的区间（如果直接找到相等的值那就搜索成功）然后往下搜索子节点，继续找到自己的区间，如果最后找到了叶子节点，说明失败了，因为（2，3，4）树的叶子节点规定为空，找到叶子节点还没有找到相等的键值说明没有搜索到。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "（2，3，4）树的删除：如果要删除的不是叶子节点往上一层，那么跟前一个交换（类似二叉搜索树的删除，这里前一个的孩子节点一定是叶子节点），然后删除前一个节点；在删除叶子节点上面一层的某个节点的基础上，如果该节点只存储了一个键值，删除了之后显然该节点不满足（2，3，4）树节点的属性了，这时应该从父节点拿一个键值下来放在该节点，然后继续分类讨论，如果兄弟节点存储了两个键值，那么拿一个到父节点就完成了删除（这叫`转移`transfer），如果兄弟节点存储一个键值，那么父节点的空缺无法弥补，只能合并该节点和兄弟节点（`这叫融合`fusion）。刚刚节点变成没有键，违反节点规则的情况称为`下溢`（underflow）。注意：从父节点拿一个下来又没有补回去（即拿下来后两个节点合并了）的操作可能导致父节点也下溢，因此要对父节点也实行刚刚的操作，然后一直递归直到不再下溢。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "（2，3，4）树插入、删除和搜索操作的时间复杂度为O(log(n))。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.6 红黑树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "AVL树和（2，3，4）树的不足：AVL树删除节点之后的再平衡可能需要多次trinode重组；（2，3，4）树删除节点之后的再平衡可能需要多次分裂或者融合的操作。相比这两种树，红黑树在删除节点之后只需要O(1)时间就可以实现自平衡。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这部分的红黑树参考的是算法导论第13章。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "红黑树定义：红黑树首先是一棵二叉搜索树，然后满足如下5个性质，\n",
    "\n",
    "1. 节点是红色或者黑色的。\n",
    "2. 根节点是黑色的。\n",
    "3. 每个叶子节点是黑色的。（哨兵）\n",
    "4. 如果一个节点是红色，则它的两个子节点都是黑色的。（两个黑色的子节点或者两个黑色的叶子节点）\n",
    "5. 对每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数量的黑色节点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "红黑树的哨兵节点可以统一用一个节点，然后跟叶子节点上一层链接起来，可以节省空间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "某个节点的黑高（black-height）：从该节点到到达其后代的叶子节点的路径上黑色节点的数量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注：（2，3，4）树和红黑树可以相互转化。参考[链接](https://blog.csdn.net/v_july_v/article/details/6531399)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "命题：一棵有n个内部节点的红黑树高度至多为2log(n + 1)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "证明：数学归纳法，对黑高进行归纳。只需证明黑高为h的内部节点为根的子树至少有$2^h - 1$个内部节点。如果黑高为0，则为叶子节点，内部节点数$2^0 - 1$，正好为0个。假设黑高为h - 1的成立，那么黑高为h的节点，分类讨论，如果该节点为红，那么两个子节点为黑，所以两个子节点黑高为h，所以内部节点数至少为$1 + 2 \\times (2^h - 1) = 2^{h + 1} - 1 > 2^h - 1$；如果该节点为黑，那么可能有两个黑色子节点，两个红色子节点，一黑一红两个子节点或者只有一个红色子节点，只有一个红色的子节点的情况只会发生在黑高为1的情况下，式子成立。有两个黑色子节点和一黑一红的内部节点数高于两个红色子节点。所以计算两个红色子节点即可，$1 + 2 \\times (2^{h-1} - 1) = 2^h - 1$。综上，其实归纳的时候就分为两个子节点和一个子节点的情况，红黑树中只有一个子节点的节点只有一种情况，那就黑色节点，有一个红色子节点和一个叶子子节点，这种情况显然成立。剩下就考虑两个子节点的情况，显然两个红色子节点黑高更低，应该是由有更少的内部节点数，所以拿来算至少。最后一步，黑高至多为log(n + 1)，由于红色节点的子节点一定是黑色节点，所以高度不超过黑高两倍，所以得证。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 11.6.1 红黑树的操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "主要是插入和删除操作，参考[链接](https://www.jianshu.com/p/e136ec79235c)。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
